package com;

import java.util.LinkedList;
import java.util.List;

/**
 * 动态方块， 有一个 N*N 的方格。 左上角上有一只蚂蚁，要移动到方格的对角上，每次只能移动一格，且只鞥你向下或者向右，
 * 求解有几种路线
 * @author YL
 **/
public class DynamicBlock {

    private final int x,  y;
    private final List<List<int[]>> links = new LinkedList<>();

    private DynamicBlock(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public void start() {
        go(0, 0, new LinkedList<>());
        System.out.println(links.size());
    }

    /**
     * 递归穷举即可
     * @param tx
     * @param ty
     * @param link
     */
    private void go(int tx, int ty, List<int[]> link) {
        link = new LinkedList<>(link);
        link.add(new int[]{tx, ty});
        if (x == tx && y == ty) {
            // 到达终点
            links.add(link);
            return;
        }

        if (x > tx) {
            go(tx + 1, ty, link);
        }
        if (y > ty) {
            go(tx, ty + 1, link);
        }
    }

    public static void main(String[] args) {
        DynamicBlock block = new DynamicBlock(3, 3);
        block.start();
        // 打印路径
        block.links.forEach(i -> {
            System.out.println("");
            int x1 = block.x;
            int y1 = block.y;
            int[][] index = new int[x1 + 1][y1 + 1];
            for (int[] ints : i) {
                int x = ints[0];
                int y = ints[1];
                index[x][y] = 1;
            }
            printBlockLink(x1, y1, index);
        });
    }

    /**
     * 打印路径
     * @param xLength
     * @param yLength
     * @param index 路径
     */
    private static void printBlockLink(int xLength, int yLength, int[][] index) {
        for (int j = 0; j <= xLength; j++) {
            for (int k = 0; k <= yLength; k++) {
                if (index[j][k] == 1) {
                    System.out.print(" o ");
                } else {
                    System.out.print(" + ");
                }
            }
            System.out.println("");
        }
    }
}
